# 复制带随机指针的链表: 
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

"""
    先看如何深拷贝，复制一个链表的方法
"""
class Solution:
    def copyRandomList1(self, head: 'Node') -> 'Node': 
        """
            使用迭代法
        """
        oldNode = head
        newNode = Node(oldNode.val)
        newHead = newNode
        while oldNode and oldNode.next:
            newNode.next = Node(oldNode.next.val)   
            newNode = newNode.next
            oldNode = oldNode.next
        
        return newHead


    def copyRandomList2(self, head: 'Node') -> 'Node': 
        """
            递归解决
            每一步可以理解为：
            1. 克隆当前节点， 
            2. next指针指向下一节点
            3. 返回当前克隆的节点

            因为下一节点还未被克隆， 所以再次调用该函数，求下一节点的克隆
        """
        def copyNode(node):
            if not node:
                return None

            newNode = Node(node.val)
            newNode.next = copyNode(node.next)

            return newNode
    

    def copyRandomList3(self, head: 'Node') -> 'Node': 
        """
            显示栈的解法。
            递归的解法，本身底层维护一个递归栈，我们可以使用定义一个栈，显示的描述这一过程
        """
        if not head: return head
        
        stack = list()
        while head:
            stack.append(head)
            head = head.next
        
        newHead = None
        while stack:
            cur = stack.pop()
            newNode = Node(cur.val)
            newNode.next = newHead
            newHead = newNode
        
        return newHead

    

# 下面是真正的解决这道题
class Solution:
    def copyRandomList1(self, head: 'Node') -> 'Node': 
        """
            递归解决
            因为需要知道当前节点的 random指针对应的新 节点， 所以需要维护 map， 来映射 旧节点和新创建的节点的一一对应。
        """
        hashMap = dict()
        def copyNode(node):
            if not node:
                return None

            newNode = Node(node.val)
            hashMap[node] = newNode

            newNode.next = copyNode(node.next)
            newNode.random = hashMap[node.random] if node.random else None

            return newNode
        
        return copyNode(head)


class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node': 
        """
            迭代解决， 同样需要维护一个 hashMap
            1. 在迭代的过程中，当 random指向遍历过的元素，那么直接从 map里找到对应的克隆元素
            2. 若random 指向的元素还未被遍历到，也依旧是还没克隆出来， 那就先克隆出来，然后指向它， 后面遍历到该元素时， 查看map 里是否提前克隆了该元素 

            迭代的解法要比递归麻烦些
        """
        if not head: return head

        hashMap = dict()
        oldNode = head
        newNode = newhead = Node(head.val)
        
        # 在这里条件不能写为  oldNode and oldNode.next  因为最后一个 节点，还要进行 random指针的操作
        while oldNode:
            # 1. 加入hashMap 映射起来
            hashMap[oldNode] = newNode
            # 2. next指针设置, 可能已经提前创建再求 random时, 当存在，才去设置next，并且需要将next也先加入到 hashMap中！！！
            if oldNode.next:
                nextNode = hashMap.get(oldNode.next, None)
                if not nextNode:
                    nextNode = Node(oldNode.next.val)
                    hashMap[oldNode.next] = nextNode
                newNode.next = nextNode
            # 3. random 指针设置
            # 如果 原节点的 node指针不为 None
            if oldNode.random:
                newRandom = hashMap.get(oldNode.random, None)
                if not newRandom:
                    newRandom = Node(oldNode.random.val)
                    hashMap[oldNode.random] = newRandom
                newNode.random = newRandom
            # 4. 更新指针前移
            oldNode = oldNode.next
            newNode = newNode.next
        
        return newhead

# 还有一种新旧交替的最优解， 替换掉 字典， 空间复杂度降低为O(1)

head = Node(1)
a = Node(2)
a.random = a
head.random = a
head.next = a

s = Solution()
rst = s.copyRandomList(head)
print(rst)